/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package algorithm;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import datastructure.BinarySearchTree;
import weka.core.Instances;
import weka.classifiers.trees.Id3;
import utility.InstancesConverter;
/**
 *
 * @author Winzelric
 */
public class DecisionTree {

    class treeQueue {
        public static final int LEFT = 0;
        public static final int RIGHT = 1;
        
        BinarySearchTree.Node node;
        BinarySearchTree.Node parent;
        ArrayList<ArrayList<String>> ar;
        int type;
        
        public treeQueue(){
            
        }
        
        public treeQueue(BinarySearchTree.Node node,BinarySearchTree.Node parent,ArrayList<ArrayList<String>> ar,int type){
            this.node = node;
            this.parent = parent;
            this.ar = ar;            
            this.type = type;
        }
    }
    
    ArrayList<ArrayList<String>> ar = new ArrayList<ArrayList<String>>();//data set
    ArrayList<String> qwe = new ArrayList<String>();//input
    BinarySearchTree tree = new BinarySearchTree();
    
    //untuk queue
    ArrayList<treeQueue> queue = new ArrayList<treeQueue>();
    BinarySearchTree.Node root = new BinarySearchTree.Node();

    public DecisionTreeModel DecisionTreeWEKA(Instances data) {
        try {
            Id3 classifier = new Id3();
            classifier.buildClassifier(data);
            return new DecisionTreeModel(classifier);
        } catch (Exception e) {
            System.out.println(e);
            return null;
        }
    }        

    public void isi(String path) {

        File toren = new File(path);
        int d = 0;
        int tesnum = 0;
        
        try {
            BufferedReader readIn = new BufferedReader(new FileReader(toren));
            String data;
            
            while ((data = readIn.readLine()) != null) {                                          
                ArrayList<String> asd = new ArrayList<String>();                
                while (d < data.length()) {
                    if (data.charAt(d) != ',') {
                        asd.add("" + data.charAt(d));                        
                    }
                    d++;
                }
                if(!isSudahAda(asd))
                    ar.add(asd);
                d = 0;
            }
            readIn.close();
        } catch (IOException e) {            
        }
    }
    
    public boolean isSudahAda(ArrayList<String> as){        
        for(int i=0;i<ar.size();i++){
            for(int j=1;j<as.size();j++){
                if(as.get(j).equals(ar.get(i).get(j)))                    
                    return true;
            }
        }
        return false;
    }
    
    public void changeArrayList(ArrayList<ArrayList<String>> ar){        
        this.ar = ar;
    }

    public DecisionTree() {
    }

    public int getsumval(ArrayList<ArrayList<String>> ar, int attributke, String val) {
        // untuk mencari jumlah suatu value pada attribut tertentu
        int sum = 0;
        int i = 0;
        while (i < ar.size()) {
            if (ar.get(i).get(attributke).equals(val)) {
                sum++;
            }
            i++;
        }
        return sum;
    }

    public int getattvaltrue(ArrayList<ArrayList<String>> ar, int attributke, String val) {
        //untuk mencari jumlah dari nilai true yang dihasilkan oleh suatu attribut dengan nilai tertentu
        int sum = 0;
        int i = 0;
        while (i < ar.size()) {
            if (ar.get(i).get(attributke).equals(val) && ar.get(i).get(0).equals("1")) {
                sum++;
            }
            i++;
        }
        return sum;
    }

    public int getattvalfalse(ArrayList<ArrayList<String>> ar, int attributke, String val) {
        //untuk mencari jumlah dari nilai false yang dihasilkan oleh suatu atribut dengan nilai tertentu
        int sum = 0;
        int i = 0;
        while (i < ar.size()) {
            if (ar.get(i).get(attributke).equals(val) && ar.get(i).get(0).equals("0")) {
                sum++;
            }
            i++;
        }
        return sum;
    }

    public float entropy(int sumtrue, int sumfalse) {
        float a = ((float) sumtrue / ((float) sumtrue + (float) sumfalse));
        float b = ((float) sumfalse / ((float) sumtrue + (float) sumfalse));
		
        if (a == 0) {
            float result = (float) (-(b * (Math.log(b) / Math.log(2))));
            return result;
        } else if (b == 0) {
            float result = (float) (-(a * (Math.log(a) / Math.log(2))));
            return result;
        } else {
            float result = (float) (-(a * (Math.log(a) / Math.log(2))) - (b * (Math.log(b) / Math.log(2))));
            return result;
        }
    }

    public float remainder(int attnum, ArrayList<ArrayList<String>> ar) {
        float sum = 0;
        for (int i = 0; i < 2; i++) {
            float a = ((float) getattvaltrue(ar, attnum, ("" + i)) / ((float) getattvaltrue(ar, attnum, ("" + i)) + (float) getattvalfalse(ar, attnum, ("" + i))));            
            //nilai pi/(pi+ni)
            float b = ((float) (getattvalfalse(ar, attnum, ("" + i))) / ((float) (getattvaltrue(ar, attnum, ("" + i))) + (float) (getattvalfalse(ar, attnum, ("" + i)))));
            //nilai ni/(pi+ni)
            float c = (((float) (getattvaltrue(ar, attnum, ("" + i))) + (float) (getattvalfalse(ar, attnum, ("" + i)))));
            //nilai (pi+ni)
            int d = (int) (getattvaltrue(ar, attnum, ("" + i)));
            //nilai pi
            int e = (int) (getattvalfalse(ar, attnum, ("" + i)));
            //nilai ni
            sum = sum + ((c / ((float) (getsumval(ar, 0, "0") + (float) (getsumval(ar, 0, "1"))))) * entropy(d, e));            
        }
        return sum;
    }

    public float infogain(float rem, float entro) {
        return (entro - rem);
    }

    public float[] daftarinfogain(int attsum) {
        //mendaftar nilai dari information gain dari setiap attribut
        float[] infogaintotal = new float[attsum];
        for (int i = 1; i < attsum; i++) {
            infogaintotal[i] = infogain(remainder(i, ar), entropy(getsumval(ar, 0, "1"), getsumval(ar, 0, "0")));                        
        }
        return infogaintotal;
    }

    public float[] daftarinfogain(int attsum, ArrayList<ArrayList<String>> dataSet) {
        //mendaftar nilai dari information gain dari setiap attribut
        float[] infogaintotal = new float[attsum];
        for (int i = 1; i < attsum; i++) {
            infogaintotal[i] = infogain(remainder(i, dataSet), 
                               entropy(getsumval(dataSet, 0, "1"), 
                               getsumval(dataSet, 0, "0")));                        
        }
        return infogaintotal;
    }    
    
    public float getminimuminfogain(float[] daftar) {
        // mengambil nilai minimum infogain lalu mengganti nilai yang diambil dengan -1
        float tempmin = 0;
        int att = 1;
        tempmin = daftar[1];
        for (int i = 1; i < daftar.length; i++) {
            if (daftar[i] < tempmin) {
                tempmin = daftar[i];
                att = i;
            }
        }
        daftar[att] = -1;
        return att;
    }

    public float getmaximuminfogain(float[] daftar) {
        // mengambil nilai minimum infogain lalu mengganti nilai yang diambil dengan -1
       
        float tempmin = 0;
        int att = 1;        
        for(int i=1;i<daftar.length;i++){
            if(daftar[i] == 0 || daftar[i] > 0 || daftar[i] < 0){
                tempmin = daftar[i];
                att = i;
                break;
            } 
        }
        
        for (int i = 1; i < daftar.length; i++) {
            if (daftar[i] > tempmin) {                
                tempmin = daftar[i];
                att = i;                
            }
        }        
        //daftar[att] = -1;
        return att;
    }
    
    // get all val of attribute
    public ArrayList<ArrayList<String>> getBoolOfAttribute(ArrayList<ArrayList<String>> dataSet, int noAtt, String val){
        ArrayList<ArrayList<String>> temp = new ArrayList<ArrayList<String>>();
        for(int i=0;i<dataSet.size();i++){
            if(dataSet.get(i).get(noAtt).equals(val))
                temp.add(dataSet.get(i));
        }                
        return temp;
    }
    
    public boolean isAllTrueOrFalse(ArrayList<ArrayList<String>> dataSet){
        boolean temp = true;
        String tempString = dataSet.get(0).get(0);// pick true/false on first in list
        for(int i=1;i<dataSet.size();i++){
            if(!dataSet.get(i).get(0).equals(tempString)){
                temp = false;
                break;
            }
        }            
        return temp;
    }        
        
    public void printTree(){
        
    }   

    public void setTree(treeQueue tq){             
        //var        
        float[] dataGainList = daftarinfogain(23, tq.ar);
        float attNo = getmaximuminfogain(dataGainList);               
        //method        
        if(tq.parent!=null){ //set parent-child                                    
            tq.node.p = tq.parent;
            if(tq.type == treeQueue.LEFT){
                tq.parent.left = tq.node;
            } else {
                tq.parent.right = tq.node;
            }
        }
        try{
            if(tq.ar.size()<3){

            }
        } catch (IndexOutOfBoundsException e){
            System.out.println("ketangkep");
        }
        if(isAllTrueOrFalse(tq.ar)){// set String key 1/0
            tq.node.key = tq.ar.get(0).get(0);            
        }
        else {
            tq.node.key = "n" + (int)attNo;// set String key n1-n(size())            
            
            tq.node.left = new BinarySearchTree.Node();
            tq.node.right = new BinarySearchTree.Node();
            queue.add(new treeQueue(tq.node.left, tq.node, getBoolOfAttribute(tq.ar, (int) attNo, "0"), treeQueue.LEFT));            
            queue.add(new treeQueue(tq.node.right, tq.node, getBoolOfAttribute(tq.ar, (int) attNo, "1"), treeQueue.RIGHT));            
//            root.left = setTree(getBoolOfAttribute(dataSet, (int) attNo, "0"), root);            
//            root.right = setTree(getBoolOfAttribute(dataSet, (int) attNo, "1"), root);                        
        }                                
    }    
            
    public BinarySearchTree.Node executeQueue(){
        BinarySearchTree.Node root = new BinarySearchTree.Node();        
        int size = queue.size();
        treeQueue temp;
        
        //exe  
        queue.add(new treeQueue(root, null, this.ar, 1));        
        while(!queue.isEmpty()){        
            temp = queue.get(0);
            queue.remove(0);
            setTree(temp);
        }
        
        return root;        
    }

    public DecisionTreeModel generateModel(ArrayList<ArrayList<String>> arr) {    
        this.ar = arr;
        DecisionTreeModel tree = new DecisionTreeModel(executeQueue());                   
        tree.tree.Print(tree.tree.root);
        return tree;
    }
    
    public DecisionTreeModel generateModel(Instances inc) {    
        ArrayList<ArrayList<String>> arr = InstancesConverter.convert(inc);
        this.ar = arr;
        DecisionTreeModel tree = new DecisionTreeModel(executeQueue());                   
        tree.tree.Print(tree.tree.root);
        return tree;
    }    
    
    

    public static void main(String args[]) {
        DecisionTree tes = new DecisionTree();        
        tes.isi("test.txt");        
        DecisionTreeModel model = tes.generateModel(tes.ar);
                
//        BinarySearchTree tree = new BinarySearchTree(tes.executeQueue());
//        tree.Print(tree.root);
    }
}
